#include <iostream>
#include <assert.h>
#include <string.h>

using std::cout;
using std::endl;

template<typename T>
class Queue{
public: 
    bool empty() const
    {
        return ((head_ + 1) % cap_) == rear_;
    }

    bool full() const
    {
        return rear_ == head_;
    }

    void push(T val)
    {
        assert(!full() && "queue is full");
        
        arr_[rear_] = val;
        rear_ = (rear_ + 1) % cap_;
        size_++;
    }

    T pop()
    {
        assert(!empty() && "queue is empty");

        head_ = (head_ + 1) % cap_;
        T tmp = arr_[head_];
        size_ --;
        return tmp;
    }

    T back() const
    {
        assert(!empty() && "queue is empty");
        if(rear_ == 0){
            return arr_[cap_ - 1];
        }
        return arr_[rear_ - 1];
    }


    T front() const
    {
        assert(!empty() && "queue is empty");
        return arr_[(head_ + 1) % cap_];
    }

    size_t size() const
    {
        return size_;
    }

    void expand() 
    {
        T *tmp = arr_;
        arr_ = new T[(cap_ - 1) * 2];

        memcpy(arr_, tmp + head_, (cap_ - head_) * sizeof(T));
        memcpy(arr_ + (cap_ - head_), tmp, rear_ * sizeof(T));

        cap_ = (cap_ - 1) * 2;
        head_ = 0;
        rear_ = size_;
        delete [] tmp;
    }

    Queue():cap_(11), arr_(new T[cap_]), head_(0), rear_(1), size_(0){}
    Queue(size_t capacity):cap_(capacity + 1), arr_(new T[cap_]), head_(0), rear_(1), size_(0){}
    ~Queue()
    {
        delete [] arr_;
    }

private:
    size_t cap_;
    T *arr_;
    size_t head_;
    size_t rear_;
    size_t size_;
};

void test1()
{
    Queue<int> que;
    for(size_t i{}; i < 20; i++){
        if(que.full()) que.expand();
        que.push(i);
    }

    printf("\nque.front() = %d\n", que.front());
    printf("que.back() = %d\n", que.back());
}

int main(int args, char *argv[])
{
    test1();
    return 0;
}